package algorithm.lanqiao.t19737;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int t = sc.nextInt();
            int k = sc.nextInt();

            // 统计同一职业的总士兵数
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < t; i++) {
                int profession = sc.nextInt();
                int count = sc.nextInt();
                map.put(profession, map.getOrDefault(profession, 0) + count);
            }

            int totalSoldiers = 0;
            int waste = 0; // W = 各职业浪费上限总和
            for (int cnt : map.values()) {
                totalSoldiers += cnt;
                waste += Math.min(cnt, 2);
            }

            int minNeeded = k + waste;
            if (minNeeded > totalSoldiers) {
                System.out.println(-1);
            } else {
                System.out.println(minNeeded);
            }
        }
        sc.close();
    }
}
